class Solution {
    public int calculateMinimumHP(int[][] arr) {
        //dp[i][j]表示到(i,j)最小花费
        //v[i][j]表示到(i,j)最大当前血量
        int n = arr.length;
        int m = arr[0].length;
        int[][] dp = new int[n][m];
        int[][] v = new int[n][m];
        v[0][0] = arr[0][0];
        for(int i = 1; i < m; i++){
            v[0][i] = v[0][i - 1] + arr[0][i];
        }
        for(int i = 1; i < n; i++){
            v[i][0] = v[i - 1][0] + arr[i][0];
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                v[i][j] = Math.max(v[i - 1][j], v[i][j - 1]) + arr[i][j];
            }
        }

        if(arr[0][0] >= 0){
            dp[0][0] = 1;
        }else{
            dp[0][0] = arr[0][0] * (-1) + 1;
        }
        for(int i = 1; i < m; i++){
            if(v[0][i - 1] + arr[0][i] > 0){
                dp[0][i] = dp[0][i - 1];
            }else{
                dp[0][i] = arr[0][i] >= 0 ? dp[0][i - 1] :  dp[0][i - 1] + (arr[0][i] * (-1));
            }
        }
        for(int i = 1; i < n; i++){
            if(v[i-1][0] + arr[i][0] > 0){
                dp[i][0] = dp[i-1][0];
            }else{
                dp[i][0] = arr[i][0] >= 0 ? dp[i - 1][0] : dp[i-1][0] + (arr[i][0] * (-1) );
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                int minv1 = 10001;
                int minv2 = 10001;
                if(v[i - 1][j] + arr[i][j] > 0){
                    minv1 = dp[i - 1][j];
                }else{
                    minv1 = arr[i][j] >= 0 ? dp[i - 1][j] : dp[i - 1][j] + arr[i][j] * (-1);
                }

                if(v[i][j - 1] + arr[i][j] > 0){
                    minv2 = dp[i][j - 1];
                }else{
                    minv2 = arr[i][j] >= 0 ? dp[i][j - 1] : dp[i][j - 1] + arr[i][j] * (-1);
                }
                dp[i][j] = Math.min(minv1, minv2);
            }
        }

        /*for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                System.out.print(v[i][j] + " ");
            }
            System.out.println();
        }*/

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }

        return dp[n - 1][m - 1];
    }
}

public class Demo1 {

    public static void main(String[] args) {
        Solution s = new Solution();

        s.calculateMinimumHP()
    }
}
